#include <queue>
#include <vector>

using namespace std;

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        // 大根堆，维护滑动窗口的最大值，同时保存 index 值
        priority_queue<pair<int, int>> p;
        vector<int> maxValues;

        for (int i = 0; i < nums.size(); i++) {
            p.push(make_pair(nums[i], i));
            if (i >= k - 1) {
                // 当 index 超出滑动窗口范围之外，出队
                while (p.top().second <= i - k) {
                    p.pop();
                }
                maxValues.push_back(p.top().first);
            }
        }

        return maxValues;
    }
};